Complex Brain Networks: A Graph-Theoretical Analysis

237

show the implementations searching for motifs on simulated data and real pub-

lic datasets. Considering that exact enumeration is computationally expensive

and the need to distinguish the types of edges which may have an effect on

the functioning of a motif, a parallel, general-purpose subgraph enumeration

method to count motifs in connectome is proposed in [16]. The authors also de-

scribe a divide-and-conquer community-based subgraph enumeration method

that provides enumeration per brain region.

Frequent complete subgraphs of the connectome are mapped by also ex-

amining sex differences in [17]. The results display complete subgraphs of the

connectome of 238 women and 175 men each with 463 nodes. The authors re-

port that 812 complete subgraphs are more frequent in men connectomes and

224 complete subgraphs are more frequent in women connectomes. The motifs

of the human brain having at most six edges is described and analyzed in [18].

The authors provide sex differences in these motifs for 426 human subjects

and conclude that for k edge connected subgraphs; male samples have slightly

more frequent motifs when k=1 or 2 whereas female samples have many more

motifs than males when k=6.

Motif search can be viewed as a frequent subgraph mining problem which

generally consists of two steps: generating a candidate subgraph and identi-

fying its isomorphism in the input graph. Subgraph mining problem is intro-

duced and various subgraph mining algorithms from a bioinformatics perspec-

tive are reviewed in [19].

9.6

Brain Network Alignment

The aim of network alignment is to find the similar structures among two or

more networks by comparing them. This problem is closely related to the sub-

graph and graph isomorphism problem and heuristic algorithms are commonly

used.

9.6.1

Background

Network alignment can be performed pairwise in which two networks are com-

pared or multiple where a number of networks are evaluated for similarity. It

is also possible to search subnetworks in local alignment whereas global align-

ment aims to find similarities between two or more networks as a whole. When

applied to biological networks, global alignment is performed to evaluate simi-

larities between similar species whereas local alignment is commonly preferred

when comparing diverse species.

The internal structures of the nodes of the networks such as the amino

acid sequences of proteins in a PPI network is evaluated in node similarity

method. On the other hand, the network structure is the main parameter